This invention relates generally to a main memory/cache memory hierarchy for use in a multi-requestor computing system and more specifically to apparatus for preventing ambiguous data in such a system where each requestor has its own dedicated cache memory.
In a multi-requestor configuration, wherein each of the requestors has associated with it its own low capacity and fast cycle time dedicated cache memory and a high capacity and slow cycle time main memory which is shared by all of the requestors, a problem arises when the contents of a main memory address may be resident or stored in one or more requestor's dedicated cache memories at one instant of time and another requestor stores information in the form of a data word into that main memory address in the main memory or in its own dedicated cache memory. If one of the plural requestors modifies that data word with, e.g., a write operation, steps must be taken in order to preserve the integrity of the data word lest a requestor obtain a data word from its own dedicated cache memory that is no longer current because of a write operation performed by a different requestor.
Several methods of handling this problem exist in the prior art and may be characterized as "write-through," "post-write" and "write-by" cache memory systems. In a "write-through" system the write operation occurs in a given requestor's dedicated cache memory. The data word located in that cache memory is modified and at the same instant the data word having the same address in main memory is also modified. Thus, the modified data word is made available to all other requestors in the system so long as the requestors obtain that data word from the main memory rather than from their own dedicated cache memories. However, since the same data word may also be resident in the dedicated cache memories of other requestors, the system must provide a means to either modify the data word in those dedicated cache memories or to notify those other requestors to obtain that particular data word from main memory and not from their dedicated cache memories.
In a "post-write" system when a write operation is performed upon a data word that is resident in the writing requestor's dedicated cache memory the data word is modified in the cache memory but is not at that time modified in main memory. At a later time, for example when a least-recently-used algorithm or similar behaving algorithm determines that a block of data words that has been modified is to be replaced, a modified data word must be written into the main memory to thereby preserve the integrity of the data within the system.
In the so-called "write-by" cache memory approach, a write operation is performed in main memory but not in the writing requestor's own dedicated cache memory. Thus, not only must other requestors in a multi-requestor environment obtain their data word at a subsequent time only from main memory but so too must the writing requestor.
A general discussion of the foregoing cache buffer memory systems for a multi-requestor environment is described in the David L. Anderson, et al, U.S. Pat. No. 3,735,360, entitled "High Speed Buffer Operation In A Multiprocessing System" which is assigned to the International Business Machines Corporation.
The present invention is directed toward preventing ambiguous data in all of these various dedicated cache memory systems by notifying other requestors that a data word that is contained in their own dedicated cache memories is invalid due to a write operation performed by another requestor in its dedicated cache memory or in main memory. The technique described in the present invention involves "invalidating" the data word that is contained in a dedicated cache memory so that that dedicated cache memory's own requestor, when accessing that particular data word, will not obtain that data word directly from its own dedicated cache memory but will instead obtain the updated or modified data word from main memory. Note that the system described in the present invention will work whether the updated data word is stored in main memory either on a "write-through," "post-write" or "write-by" basis.
When one requestor performs a write operation on a data word in its own dedicated cache memory, that requestor must then have access to all other dedicated cache memories in order to perform this invalidate operation. If the written or modified data word is found contained in another dedicated cache memory, then that data word must be invalidated at that location. If the particular data word written is not found in another dedicated cache memory, then no invalidate operation need be performed, but it still has been necessary to perform the search operation in order to ascertain that the written data word is not contained in the other dedicated cache memories.
A single dedicated cache memory is comprised mainly of two basic parts, a data buffer and a tag buffer. The data buffer contains those data words that are held in the dedicated cache memory for fast access by that dedicated cache memory's own requestor. The tag buffer contained in the dedicated cache memory contains a list or a table of addresses of the data words that are contained in the data buffer. Thus, when a requestor wishes to access a particular data word it accesses the tag buffer and searches the list of available addresses to ascertain whether that particular data word is resident in the data buffer. If a match is made in the tag buffer then the data word is accessed directly by the requestor from the data buffer. If a match does not occur in the tag buffer the requestor then must either sequentially or concurrently with access to the dedicated cache memory, request that data word from main memory and obtain that data word from main memory.
In general, a requestor needs access to both the tag buffer and the data buffer of its own dedicated cache memory. However, any requestor other than the resident requestor that is specifically dedicated to that dedicated cache memory (a non-resident requestor) needs to have access only to the tag buffer portion of any other requestor's dedicated cache memory. This is because a requestor never accesses data words from another requestor's dedicated cache memory. A requestor is required to have access to only the tag buffer portion of another requestor's dedicated cache memory for purposes of invalidating the addresses listed therein.